The present invention relates to wireless and wireline communication systems. More specifically, the present invention relates to an improved method for estimating symbol sequences of multiple sources sharing the same communication media. The invention is particularly useful for code-division-multiple-access (CDMA) receivers where the channel length is only limited to two neighboring symbols.
In a scenario where m receivers are utilized, the received signal at each receiver is the sum of the output of channels driven by u different user signals plus the noise at the receiver. The channel between receiver i and user j can be denoted as hij. In general, hij≠hqn if i≠q or j≠n. Noise signals at different receivers are assumed to be independent of one another. If the user signals are actually CDMA signals and the largest duration of hij, i=1, . . . , m and j=1, . . . , u is short enough compared to the symbol duration of those CDMA signals, the orthogonality of the spreading codes can guarantee the separation of CDMA signals at each receiver. Intersymbol interference (ISI) and multiple access interference (MAI) are negligible. When the largest duration of the signature waveforms is comparable with, or even larger than the symbol duration, ISI and MAI can become severe. The performance of detection made on symbols individually will not be good due to ISI and MAI. Such a situation calls for joint detection by which channel effects are modeled adequately and symbol sequences are estimated jointly. In minimum-mean-square-error (MMSE) based joint detection, which will be referred to as joint detection in the following, an inverse filtering process is used to remove intersymbol interference and multiple access interference. To do this, a coefficient matrix H formed from the channel responses is inverted. More precisely, the pseudo-inverse of this coefficient matrix: (H*H)−1H* must be found. The main problem associated with joint detection is that the computation thus involved is intensive. The dimension of H is determined by the number of users, the length of spreading sequences, the length of symbol sequences, and the number of receivers involved (even with only one receiver, the effect of multiple receivers can be achieved by sampling a received continuous signal at a multiple times of the symbol rate.). With a moderate number of users and a moderate number of symbols, the dimension of the coefficient matrix can be large. To speed up the inversion of the coefficient matrix, a Cholesky decomposition on H*H can be used. However, the computation amount involved in the Cholesky decomposition can still be substantial, as the requirement on matrix operations such as matrix inverses increases linearly with the number of symbols. It is therefore desirable to have a method to speed up the joint detection computation.
Prior to this invention, a class of multiuser detectors have been developed. The most prominent ones among many others include R. Lupas and Verdu, “Linear multiuser detectors for synchronous CDMA channels”, IEEE Trans. on Information Theory, 1(35):123-136, January 1989.; Z. Xie et al. “A family of sub-optimum detectors for coherent multiuser comnmunication”, IEEE Journal of Selected Areas in Communications, pages 683-690, May 1990; and Z. Zvonar and D. Brady, “Suboptimum multiuser detector for syncrhonous CDMA frequency-selective Rayleigh fading channels”, IEEE Trans. on Communications, Vol. 43 No. 2/3/4, pp.154-157, February/March/April, 1995, Angel M. Bravo, “Limited linear cancellation of multiuser interference in DS/CDMA asynchronous system”, pp. 1435-1443, November, 1997. They either design various finite-impulse-response filters to process the received signals, which are in essence approximate solutions of the MMSE based joint detection solution, or use Cholesky decomposition to solve the equations involving the large coefficient matrix, e.g. Paul D. Alexander and Lars Rasmussen, “On the windowed Cholesky factorization of the time-varying asynchronous CDMA channel”, IEEE Trans. on communications, vol. 46, no. 6, pp.735-737, June, 1998, which gives the exact MMSE joint detection result with high computational complexity, i.e. complexity of matrix operations such as matrix inversion increases linearly with the number of symbols.
As in many communication systems, the length of ISI and MAI is often limited to several symbols, besides being Toeptliz or block Toeplitz matrix, the coefficient matrix is also banded. Fast algorithms developed for generic Toeplitz or block Toeplitz matrices, e.g. Georg Heinig and Karla Rost, “Algebraic Methods for Toeplitz-like Matrices and Operators”, Birkhauser, 1984, do not take advantage of the fact that the coefficient matrix is banded. The afore-mentioned Cholesky factorization based algorithm, while taking advantage of the banded nature of the coefficient matrix, does not take advantage of the fact that the coefficient matrix is also Toeplitz or block Toeplitz, which leads to considerable increase of computational demand as the number of matrix operations such as matrix inversion increases with the number of symbols to be estimated Simpler versions of the method disclosed in this invention, have been used to solve numerically Poisson equations, e.g. Roland A. Sweet, “A cyclic reduction algorithm for solving block tridiagonal systems of arbitrary dimension”, SIAM journal on Numerical Analysis, Vol. 14, pp. 706-720, September, 1977.